# 26/100 链表-环形链表II
# leetcode第142题: https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/16
from typing import Optional
from leetcode import test
from leetcode.bds import ListNode


def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return None
    curr = head
    visited = set()
    visited.add(head)
    while curr.next:
        if curr.next in visited:
            return curr.next
        else:
            visited.add(curr.next)
            curr = curr.next
    return None


def detectCycle_dbpnt(head: Optional[ListNode]) -> Optional[ListNode]:
    """使用快慢指针的方法, 只使用 O(1) 空间"""
    if not head:
        return None

    fast = head
    slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast is slow:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None


if __name__ == '__main__':
    head1 = ListNode(3)
    pos1 = head1.append(2)
    tail1 = pos1.append(0).append(-4)
    tail1.next = pos1

    head2 = ListNode(1)
    pos2 = head2.append(2)
    pos2.next = head2

    head3 = ListNode(1)

    head4 = ListNode(1)
    head4.append(2)

    print(detectCycle(head1) is pos1)
    print(detectCycle(head2) is head2)
    print(detectCycle(head3) is None)
    print(detectCycle(head4) is None)

    print(detectCycle_dbpnt(head1) is pos1)
    print(detectCycle_dbpnt(head2) is head2)
    print(detectCycle_dbpnt(head3) is None)
    print(detectCycle_dbpnt(head4) is None)
